//如果交换字符串 X 中的两个不同位置的字母，使得它和字符串 Y 相等，那么称 X 和 Y 两个字符串相似。如果这两个字符串本身是相等的，那它们也是相似的。
//
//
// 例如，"tars" 和 "rats" 是相似的 (交换 0 与 2 的位置)； "rats" 和 "arts" 也是相似的，但是 "star" 不与
//"tars"，"rats"，或 "arts" 相似。
//
// 总之，它们通过相似性形成了两个关联组：{"tars", "rats", "arts"} 和 {"star"}。注意，"tars" 和 "arts" 是在同
//一组中，即使它们并不相似。形式上，对每个组而言，要确定一个单词在组中，只需要这个词和该组中至少一个单词相似。
//
// 给你一个字符串列表 strs。列表中的每个字符串都是 strs 中其它所有字符串的一个字母异位词。请问 strs 中有多少个相似字符串组？
//
//
//
// 示例 1：
//
//
//输入：strs = ["tars","rats","arts","star"]
//输出：2
//
//
// 示例 2：
//
//
//输入：strs = ["omv","ovm"]
//输出：1
//
//
//
//
// 提示：
//
//
// 1 <= strs.length <= 300
// 1 <= strs[i].length <= 300
// strs[i] 只包含小写字母。
// strs 中的所有单词都具有相同的长度，且是彼此的字母异位词。
//
//
// Related Topics 深度优先搜索 广度优先搜索 并查集 数组 字符串 👍 172 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
function numSimilarGroups(strs: string[]): number {
    const n = strs.length;
    const m = strs[0].length;
    //? 存储并查集的根节点 一开始各自为营
    const f = new Array(n).fill(0).map((element, index) => index);
    //? 双循环遍历每一对字符串
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            //? 对于每一对字符串，函数通过 find 函数找到它们所属的并查集的根节点，
            //? 如果根节点相同，则表示它们已经在同一个组中，可以继续下一对字符串的比较
            const fi = find(i), fj = find(j);
            if (fi === fj) {
                continue;
            }
            //? 如果根节点不同，并且通过 check 函数判断它们是否相似（只有两个字符不同），则将两个根节点合并
            if (check(strs[i], strs[j], m)) {
                //? 将i的根节点设置为j的根节点
                f[fi] = fj;
            }
        }
    }
    let ret = 0;
    //? 遍历并查集数组 f ，如果某个元素的值等于其索引，则表示它是一个根节点，即一个独立的组，将计数器 ret 增加
    for (let i = 0; i < n; i++) {
        if (f[i] === i) {
            ret++;
        }
    }
    return ret;
    //? 找并查集根节点 一直往上找
    function find(x) {
        return f[x] === x ? x : (f[x] = find(f[x]));
    }
    //?   check 函数用于判断两个字符串是否相似。
    //? 它遍历两个字符串的每个字符，如果有不同的字符，则增加计数器 num 。如果 num 大于2，则表示两个字符串不相似，返回 false ，否则返回 true
    function check(a, b, len) {
        let num = 0;
        for (let i = 0; i < len; i++) {
            if (a[i] !== b[i]) {
                num++;
                if (num > 2) {
                    return false;
                }
            }
        }
        return true;
    }

};
//leetcode submit region end(Prohibit modification and deletion)
